package 中等.模拟;

/**
 * 给你一个偶数 n​，已知存在一个长度为 n 的排列 perm ，其中 perm[i] == i​（下标 从 0 开始 计数）。
 * 一步操作中，你将创建一个新数组 arr ，对于每个 i ：
 * 如果 i % 2 == 0 ，那么 arr[i] = perm[i / 2]
 * 如果 i % 2 == 1 ，那么 arr[i] = perm[n / 2 + (i - 1) / 2]
 * 然后将 arr​赋值​​给 perm 。
 * 要想使 perm 回到排列初始值，至少需要执行多少步操作？返回最小的 非零 操作步数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-number-of-operations-to-reinitialize-a-permutation
 */
public class 还原排列的最少操作步数_1806 {

    public static void main(String[] args) {

        System.out.println(reinitializePermutation2(6));

    }

    /**
     * 直接模拟
     */
    public static int reinitializePermutation(int n) {
        int[] perm = new int[n];
        for (int i = 0; i < perm.length; i++) {
            perm[i] = i;
        }
        int cnt = 0;

        while (true) {
            cnt++;
            int[] arr = new int[n];
            boolean flag = true;
            for (int i = 0; i < arr.length; i++) {
                if (i % 2 == 0) {
                    arr[i] = perm[i / 2];
                } else {
                    arr[i] = perm[n / 2 + (i - 1) / 2];
                }
                if (arr[i] != i) {
                    flag = false;
                }
            }
            if (flag) {
                return cnt;
            }
            perm = arr;
        }
    }

    /**
     * 找规律
     * perm数组还原的过程中其实存在多个环，且每个环互不相交，环中任意一个
     * 元素，其操作数是一样的，一个环只需要计算一次操作数
     */
    public static int reinitializePermutation2(int n) {
        boolean[] visited = new boolean[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            int cnt = 0, num = i;
            while (!visited[num]) {
                cnt++;
                visited[num] = true;
                if (num % 2 == 0) {
                    num /= 2;
                } else {
                    num = n / 2 + (num - 1) / 2;
                }
            }
            max = Math.max(max, cnt);
        }
        return max;
    }

}
